class QuickSort {
	static sort(arr) {
  	QuickSort.quickSort(arr, 0, arr.length - 1);
  }
  
  static quickSort(arr, l, r) {
  	if (l >= r) return; // 数组为空或者是一个元素，那么不需要进行分区操作
    const p = QuickSort.partition(arr, l, r);
    QuickSort.quickSort(arr, l, p - 1);
    QuickSort.quickSort(arr, p + 1, r);
  }
  
  static partition(arr, l, r) {
    // 取随机值
    const tempPartition = l + Math.floor(Math.random() * (r - l + 1))
    QuickSort.swap(arr, l, tempPartition);
    // 主要还是分区点的变化，使用左右两个指针，且保证：[l+1, j] <= v; [i, l] >= v
    let i = l + 1;
    let j = r;
    // [l+1, i - 1] <= v [j+1, r] >= v;
    while(true) {// 从l+1开始遍历
    	while(arr[i] <= arr[l]) {
      	i++;
      }
      while(arr[j] >= arr[l]) {
      	j--;
      }
      if (i >= j) {
      	break;
      }
      QuickSort.swap(arr, i, j);
      i++;
      j--;
    }
    QuickSort.swap(arr, l, j);
    return j;
  }
  
  static swap(arr, i, j) {
  	const temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
  }
}

function generateArr(num, end) {
  const arr = [];
  for (let i = 0; i < num; i++) {
    // eslint-disable-next-line no-unused-expressions
    arr[i] = Math.floor(Math.random() * end);
  }
  return arr;
}
const arr = generateArr(20, 100);
console.log(arr);
QuickSort.sort(arr);
console.log(arr);